1. Field of the Invention
This invention generally relates to methods and apparatus for matching fingerprints with images of fingerprints stored electronically in a database, and more specifically relates to a fingerprint matcher that uses a ladder chaining method for matching fingerprints.
2. Description of the Related Art
In many contexts, especially in criminal situations, latent fingerprints of unknown origin are often encountered. Since any one person's fingerprints are unique to that person, the identity of a person who leaves a fingerprint may be ascertained if this print of unknown origin can be matched with a fingerprint of known origin. Two instances of the fingerprint (or "print") are used to make an identification. The print of unknown origin is commonly referred to as the "search" print and may be an image of an inked impression, an image acquired by an electronic scanning device, or an image of a latent print left at the scene of a crime. Prints stored in electronic form, against which the search print can be compared, are commonly referred to as "file" prints. File prints are typically stored in a database which can associate images of these prints, or other data extracted therefrom, with the identity of individual persons.
The appearance of fingerprints is well known. Closely spaced, generally parallel, "ridges" of friction skin appear black on an inked fingerprint. Often they exhibit a generally circular flow around the center, or "core", of the print. At specific points, a ridge may terminate at a "ridge end" or may divide into two ridges at a "bifurcation". Other morphological events, such as "bridges" and "trifurcations" are known as well, as shown in U.S. Pat. No. 4,752,966, "Fingerprint Identification System" (issued Jun. 21, 1988 to Schiller and assigned to Fingermatrix, Inc.), and U.S. Pat. No. 4,135,147, "Minutiae Pattern Matcher" (issued Jan. 1, 1979 to Riganati et al. and assigned to Rockwell International Corp.), which are both incorporated herein by reference. These morphological events are known as "minutiae", or in the singular, "minutia", and typically number between 50 and 200 on a person's fingers. The disposition of these minutiae across a fingerprint is unique to the individual and to the finger, and as a result, can form the basis for the identification of the individual.
A fingerprint may be represented as a list of minutiae. Such a list of fingerprint minutiae is a highly compressed data representation of the original fingerprint image. Although the minutiae may be identified by a human operator looking at a displayed image of the fingerprint, an automated system is preferable, and typically implements, in very general terms, four steps: i) preliminary image processing, ii) binarization, to turn all dark pixels black and all light pixels white, iii) skeletonization, wherein thick black ridges in the binarized image are "thinned" down to one-pixel thickness, and iv) minutia identification from the skeletonized image.
A fingerprint "matcher" is an automated mechanism for comparing search prints with file prints. A matcher which utilizes minutiae in the comparison compares a representation of the minutiae data from a single search print with that of a single file print. The representation of minutiae data is a list of minutiae and other forms of information. Among these may be the geometric locations of the minutiae in the frame of the image, the orientation of minutiae with respect to the frame of the image, and the relationships of the minutiae between themselves. The functional requirements of a given matcher dictate the format of minutiae data input to the matcher.
Many different fingerprint matchers are known. The most prevalent of these compare search print and file print minutiae, while others use direct optical comparison methods of images as wholes. Fingerprint matchers that compare search and file minutiae generally may be categorized using two discriminants: 1) whether the matcher is "spatial" or "topological" and 2) whether the matcher uses information "local" to minutiae exclusively. These discriminants form a framework for understanding the present fingerprint matcher in the context of those that are known in the prior art.
The first discriminant is whether the matcher is "spatial" or "topological". A purely spatial matcher uses the geometric relationships among minutiae of a print without regard to the identity of ridges which then terminate, bifurcate, or otherwise form a morphological event. The Cartesian coordinates of each minutia are recorded along with an estimate of the angle that each minutia exhibits with respect to the frame of the print image. For instance, the angle of a ridge end can be estimated from a short segment of the dark pixels leading away from the minutia along the ridge. A well-known example of a spatial matcher is described in Wegstein, J. H., "The M40 Fingerprint Matcher," N.B.S. Technical Note 878 (National Bureau of Standards, July 1975), which is incorporated herein by reference.
A topological matcher uses the connectivity of ridges among minutiae to establish relationships among them in a single print. If two ridge ends terminate the same ridge, on which there is no other minutia, then there is a specific relationship between the minutiae that may be exploited by the matcher. This relationship, of being connected by the ridge, holds irrespective of the distance between the minutiae. Examples of topological matchers are discussed in Malcolm K. Sparrow and Penelope J. Sparrow, "A Topological Approach to the Matching of Single Fingerprints: Developments of Algorithms for Use on Latent Fingermarks", N.B.S. Special Pub. 500-126 (National Bureau of Standards 1985); in U.S. Pat. No. 4,747,147 "Fingerprint Recognition System" (issued May 24, 1988 to Sparrow); and in U.S. Pat. No. 4,817,183 "Fingerprint Recognition and Retrieval System" (issued Mar. 28, 1989 to Sparrow). All of these references are incorporated herein by reference. These references show matchers which rely on "ridge counts", which refer to the number of ridges crossed by a line drawn from the core of the print to each minutia.
Not only are spatial and topological matchers known in the art, hybrid forms known as well. A hybrid form of a spatial and topological matcher would use both geometric and ridge information about minutiae. For example, U.S. Pat. No. 4,646,352 "Method and Device for Matching Fingerprints with Precise Minutia Pairs Selected From Coarse Pairs" (issued Feb. 24, 1987 to Asai et al. and assigned to NEC Corp.) discloses a matcher that utilizes relations within pairs of minutiae, and is incorporated herein by reference. To characterize each pair of minutiae, the matcher uses both a local frame of coordinates and the ridge counts between the minutiae.
The second discriminant for categorizing a fingerprint matcher is whether or not it uses information "local" to minutiae exclusively. If a spatial matcher compares the coordinates in the frame of the image of search minutiae to those of file minutiae, that matcher uses "global" information, not information strictly local to individual minutiae. The global information is the reference to the frame of the image. For example, U.S. Pat. No. 4,790,564 "Automatic Fingerprint Identification System Including Processes and Apparatus for Matching Fingerprints" (issued Dec. 13, 1988 to Larcher et al. and assigned to Morpho Systems) shows a spatial matcher that in effect superimposes a rotated and translated set of search minutiae onto a set of file minutiae, and is incorporated herein by reference.
A spatial matcher that uses only local information would construct and use relative geometric relationships within small groups of minutiae, such as pairs. The geometry would be referenced only to a local frame, not to that of the full image, making the matcher less vulnerable to distortions of the skin than a matcher that uses global information. For example, the matcher disclosed in the '352 patent to Asai et al. establishes, for each minutia, four other close minutiae. These are the closest minutia in each of the four quadrants of the frame local to the central minutia. All measurements used for matching between search and file are made between local pairs.
A topological matcher that uses global information uses the location of the core of the fingerprint or a line of symmetry to reference ridge counts for minutiae. The information is referenced to the whole fingerprint morphology. The matchers disclosed in the '147 and '183 patents to Sparrow use such global information to automate as much as possible the matching of latent search prints. Since latent fingerprints left at crime scenes are typically of poor image quality, these matchers are designed to make use of as much information as possible. The location of the core or the line of symmetry provides good registration for minutia data.
Matchers are known that use both local and global relationships of minutiae. For example, the '147 patent to Riganati et al. discloses a matcher that performs a "global coherency analysis" to form a best fit of local relationships across the whole print to determine whether the search print matches any stored file prints.
A matcher must not only compare minutiae of search and file prints, but must also determine, based on this comparison, whether or not the search print matches the file print. Sparrow's LM6 matcher, as disclosed in his '147 and '183 patents, uses a scoring scheme for each matching search-file pair of minutiae, to determine whether the search print matches the file print. Briefly, a given search-file mating of minutiae S0 is linked to other minutiae S1 and bears an initial score derived from those links. Then the other minutiae S1 are themselves linked to yet other minutiae S2. The initial score of S0 is then modified by adding the scores of S1 to S2 links that are compatible" with the S0 to S1 link. Hence, the compatible scores at the S1 level get "pulled in" to S0. Since each of these links is actually a relationship between search minutiae and a separate relationship between file minutiae, the identity of which search minutia is mated to which file minutia can render two links incompatible. Sparrow's LM6 matcher conducts a table sort which enforces such compatibility, thus ensuring the validity of the scoring scheme. Sparrow's LM6 matcher uses the scoring scheme to increase the accuracy of positively identifying a match between search and file prints.
An important objective for a fingerprint matcher is to be robust to any distortions that may exist in the search print. Skin is stretchy, and the disposition of minutiae across the image of the fingerprint is notoriously variable from instance to instance. Fingerprints that are typically digitally acquired and image-processed, may also suffer from several untoward deviations caused by abraided areas of skin, smudged areas on inkings, and optical and sampling limitations of direct sensors. Minutiae apparently "mutate" from ridge ending to bifurcation or vice versa. True minutiae can be missed or false minutiae can appear. An automated fingerprint matcher, when integrated with its image processing, should be robust as much as possible to these problems that inherently arise.
Different types of matchers will exhibit different vulnerabilities to skin distortions and other problems. A spatial matcher is affected directly by geometric distortion, while a topological matcher has mechanisms to walk along with the "ridge flow", regardless of such distortion. If the ridge flow is interrupted, however, the topological matcher will lose track of the ridge that it had been tracing. An important case is when a print is cut off at the edge of the finger (e.g., the tip is missing); the ridges disappear at the edge of the acquired image, causing the topological matcher to lose track of the ridge and is thus unable to use minutiae connected by interrupted ridges in comparing the search print to a file print. A spatial matcher would not be so affected by interrupted ridges caused by partial prints, but is inherently more vulnerable to skin distortions that alter the geometric relationship between minutiae.
Therefore, there exists a need to provide a fingerprint matcher that is robust to many of the uncontrollable factors in either search or file prints, such as smudges, partial prints, distortions in the skin, etc.